package primary.code06_graph;

import java.util.*;

/**
 * @author Yudi Wang
 * @date 2021/7/16 16:41
 *
 * 深度优先遍历
 */
public class Code03_DFS {

    private static void dfs(Node node) {
        if(node ==null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        HashSet<Node> set =new HashSet<>();
        stack.push(node);
        set.add(node);
        System.out.println(node.val);
        while (!stack.isEmpty()){
            Node cur = stack.pop();
            for (Node next : cur.next) {
                if(!set.contains(next)){
                    stack.push(cur);
                    stack.push(next);
                    set.add(next);
                    System.out.println(next.val);
                }
            }
        }
    }

    private static void dfsTest(Node node){
        if (node == null) return;
        Stack<Node> stack = new Stack<>();
        Set<Node> visited = new HashSet<>();
        System.out.print("\t" + node.val);
        stack.push(node);
        visited.add(node);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            for (Node next : cur.next) {
                if (!visited.contains(next)) {
                    visited.add(next);
                    System.out.print("\t" + node.val);
                    stack.push(node);
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        //转换为自己熟悉的数据结构
        //第一个元素代表权值，第二个元素代表一条边的出边节点，第三个元素代表一条边的入边节点
        int[][] arr = {
                {4, 1, 2},
                {3, 2, 3},
                {1, 3, 1},
                {1, 2, 4},
                {1, 4, 5}
        };
        Graph g = GraphUtils.transferGraphUndirected(arr);//无向图
        //宽度优先遍历
        dfs(g.nodes.get(1));
        System.out.println("====");
        dfsTest(g.nodes.get(1));
    }
}
